SBM, DCBM, and PABM are generalized random dot product graphs in which the communities correspond to linear structures in the latent space.
Let \(p, q \geq 0\), \(d = p + q \geq 1\), \(1 \leq r < d\), \(K \geq 2\), and \(n > K\) be integers. Let \(\mathcal{X} = \{x, y \in \mathbb{R}^d : x^\top I_{p,q} y \in [0, 1]\}\) and define manifolds \(\mathcal{M}_1, ..., \mathcal{M}_K \subset \mathcal{X}\) each by continuous function \(g_k : [0, 1]^r \to \mathcal{X}\). Define probability distribution \(F\) with support \([0, 1]^r\). Then the following mixture model is a manifold block model:
Theorem.
Let an MBM be such that the manifolds are described as polynomial curves of order \(R\).
Suppose that for each community \(k\), we have labels for at least \(R + 1\) vertices.
Then \(K\)-curves clustering outputs estimators such that
\[L(\hat{z}_1, ..., \hat{z}_n, \hat{g}_1, ..., \hat{g}_K; A) \stackrel{p}{\to} 0.\]
Latent vectors were drawn uniformly on three intersecting quadratic curves in \(\mathbb{R}^3\) (left) to construct a GRDPG (middle). Curves were then fitted to the ASE (right) and embedding vectors were assigned labels based on proximity to the curves.
Block models can be expressed as GRDPGs in which the communities are linear structures in the latent space. We propose the manifold block model to extend this to nonlinear latent structures and the \(K\)-curves clustering algorithm to estimate these structures for community detection.